import java.math.BigInteger;


public class Week1 {

	public Week1() {
		BigInteger arg1 = new BigInteger("2");
		
		machtv2(arg1,100);
		machtv2(arg1,1000);
		machtv3(arg1,100);
		machtv3(arg1,1000);
	}

	BigInteger machtv2(BigInteger a, int n) // O(N)
	{
		int multiply = 0;
		assert n >= 0;
		
		BigInteger m = new BigInteger("1");
		
		if (n == 0)
		{
			return m;
		}
		
		for (int i = 0; i < n; i++)
		{
			m = m.multiply(a);
			
			multiply++;
		}

		print(a,n,m,multiply);
		return m;
	}

	BigInteger machtv3(BigInteger a, int n) // O(logN)
	{
		int multiply = 1;
		BigInteger tmpA = new BigInteger(a.toString());
		int tmpN = n;
		assert n >= 0;

		BigInteger m = new BigInteger("1");
		
		if (n == 0)
		{
			return m;
		}
		
		while (n > 1)
		{
			if (n % 2 == 1)
			{
				m = m.multiply(a);
				multiply++;
			}
			
			n = n / 2;
			
			a = a.multiply(a);
			multiply++;
		}
		
		m = m.multiply(a);
		
		print(tmpA,tmpN,m,multiply);
		
		return m;
	}
	
	
	
	public void print(BigInteger a, int n, BigInteger x, int m)
	{
		StringBuilder inter = new StringBuilder(x.toString());

		System.out.println(a.toString()+"^"+n+" \t= "+formatNotation(x, 25)+" \t(aantal multiply's: "+m+" )");
	}
	
	public String formatNotation(BigInteger x, int decimals)
	{
		StringBuilder inter = new StringBuilder(x.toString());
		
		// We also display the first number before the point.
		decimals++;
		
		int z = inter.length() - decimals;
		int y = inter.length() -1;
		
		if (z < 0)
		{
			while (z < 0)
			{
				inter.append("0");
				
				z++;
			}
		}
		else if (z > 0)
		{
			inter = new StringBuilder(inter.substring(0, decimals));
		}
		
		inter.insert(1, '.');
		
		return inter.toString()+" . 10^"+y;
	}

	public static void main(String[] args) {
		new Week1();
	}
}
